package sort;

/**
 * @ClassName: MergeSort
 * @ProjectName DataStructure
 * @Description: 归并排序
 * @Author minghua
 * @Date 2021/3/102:47 下午
 * @Version V1.0
 */
public class MergeSort {
    /***
     * 拆分问题，归并一个有序的数组
     * @param array 待排序的部分有序数组
     */
    public static int[] mergeTest(int[] array){
        int midPosition = array.length / 2;

        int i = 0;
        int j = midPosition;
        int k = 0;

        int[]rs = new int[array.length];
        while (i < midPosition && j < array.length){
//            if(array[i]<=array[j]){
//                rs[k] = array[i];
//                k++;
//                i++;
//            }else {
//                rs[k] = array[j];
//                k++;
//                j++;
//            }
            rs[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }
//        if(i<midPosition){
//            System.arraycopy(array,i,rs,k,midPosition-i);
//        }else{
//            System.arraycopy(array,j,rs,k,array.length-j);
//        }
        while(i < midPosition){
            rs[k++] = array[i++];
        }
        while (j < array.length){
            rs[k++] = array[j++];
        }
        return rs;
    }

    public static void sort(int[] array,int left,int right){
        if(right==left){
            return;
        }
        //防止长度超过int最大值
        int mid = left + (right - left)/2;
        sort(array,0,mid);
        sort(array,mid+1,right);
        merge(array,left,mid+1,right);
    }


    public static void merge(int[] array,int leftPtr,int rightPtr,int rightBound){
        int mid = rightPtr - 1;
        int[] tmp = new int[rightBound - leftPtr + 1];

        int i = leftPtr;
        int j = rightPtr;
        int k = 0;

        while (i<=mid&&j<=rightBound){
            tmp[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }

        while (i<=mid) {
            tmp[k++] = array[i++];
        }
        while (j<=rightBound) {
            tmp[k++] = array[j++];
        }

        for (int l = 0; l < tmp.length; l++) {
            array[leftPtr+l] = tmp[l];
        }
    }
}
